package com.yangzhe.algorithm.c035;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// 插入、删除和获取随机元素O(1)时间的结构
public class Code03_InsertDeleteRandom_LeetCode {
    public static void main(String[] args) {
        RandomizedSet set = new RandomizedSet();
        System.out.println(set.remove(0));
        System.out.println(set.remove(0));
        System.out.println(set.insert(0));
        System.out.println(set.getRandom());
        System.out.println(set.remove(0));
        System.out.println(set.insert(0));
    }

    // 测试链接 : https://leetcode.cn/problems/insert-delete-getrandom-o1/
    static class RandomizedSet {

        // key 是 set中的val value是List中的index
        private Map<Integer, Integer> map;

        // 保存数值，用于O(1)获取随机元素
        private List<Integer> list;

        public RandomizedSet() {
            map = new HashMap<>();
            list = new ArrayList<>();
        }

        public boolean insert(int val) {
            if (map.containsKey(val)) {
                return false;
            }
            list.add(val);
            map.put(val, list.size() - 1);
            return true;
        }

        public boolean remove(int val) {
            if (!map.containsKey(val)) {
                return false;
            }

            int index = map.get(val);
            if (index != list.size() - 1) {
                // 如果存在多个元素，则把最后一个元素覆盖到要删除的位置，然后删除最后一个元素
                int lastValue = list.get(list.size() - 1);
                list.set(index, lastValue);
                map.put(lastValue, index);
            }
            list.remove(list.size() - 1);
            map.remove(val);

            return true;
        }

        public int getRandom() {
            // 随机一个index 获取元素就是O(1)
            int index = (int) ((list.size()) * Math.random());
            return list.get(index);
        }

    }
}
